//
// Description: 01背包问题
// Created by Loading on 2021/8/9.
//
// https://www.acwing.com/problem/content/description/2/

// 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
// 第 i 件物品的体积是 vi，价值是 wi。
// 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
// 输出最大价值。

// 输入格式
// 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
// 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
//
// 输出格式
// 输出一个整数，表示最大价值。

// 数据范围
// 0<N,V≤1000
// 0<vi,wi≤1000

// 输入样例
// 4 5
// 1 2
// 2 4
// 3 4
// 4 5
// 输出样例：
// 8

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    // 体积
    vector<int> v(n + 1);
    // 价值
    vector<int> w(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i] >> w[i];
    }

    vector<int> dp(m + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= v[i]; --j) {
            // 假设选取第 i 个物品，体积需大于第 i 个物品
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }

    cout << dp[m] << endl;
}